#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

namespace zy
{
	template<class K>
	struct BSTNode
	{
		BSTNode<K>* _left;
		BSTNode<K>* _right;
		K _key;

		BSTNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};

	template<class K>
	class BinarySearchTree
	{
		typedef BSTNode<K> Node;
	public:
		BinarySearchTree()
			:_root(nullptr)
		{}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
					cur = cur->_left;
				else if (key > cur->_key)
					cur = cur->_right;
				else
					return cur;
			}
			return nullptr;
		}

		

		Node* GetRoot()
		{
			return _root;
		}

		

		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* p = new Node(key);
			Node* cur = _root;
			Node* parent = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;
			}
			if (key < parent->_key)
				parent->_left = p;
			else
				parent->_right = p;
			return true;
		}

		void InOrder()
		{
			InOrder1(_root);
			cout << endl;
		}

	private:
		void InOrder1(Node* root)
		{
			if (root == nullptr)
				return;

			InOrder1(root->_left);
			cout << root->_key << " ";
			InOrder1(root->_right);
		}

		Node* _root;
	};
}

